home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / c_toolbx.arc / MEMSORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-03-30  |  1.6 KB  |  51 lines
  1. /*  memsort.c - preforms a quicksort with an array of pointers */
  2. /*  and a caller-supplied compare function */
  3. #include   "stdio.h"
  4. #include   "cminor.h"
  5.  
  6. #define    LIMIT 8        /* crossover point for insertion sort */
  7.  
  8. int  memsort(pa,na,pcomp)
  9.   char    *pa[] ;         /* array of pointers to data to be sorted */
  10.   int    na ;            /* number of elements to be sorted */
  11.   int    (*pcomp) ()  ;        /* pointer to compare function */
  12.   {
  13.      int   i,j     ;        /* indeces for loops */
  14.      char  *ptemp    ;        /* temporary storage for one pointer */
  15.      int   nr ;         /* number elements in right partition */
  16.      char  *ppart    ;    /* pointer to element used as partition value */
  17.  
  18.      if( na < LIMIT )        /* use insert sort for small partitions */
  19.     {  insert(pa,na,pcomp) ;
  20.        return ;
  21.     }
  22.  
  23.      ppart = pa[na/2] ;     /* pick middle element for partition */
  24.      i = -1 ; j = na ;
  25.      while( 1==1 )
  26.     {  /* find first element to move right */
  27.        do { i = i + 1 ; } while( (*pcomp) (pa[i],ppart) < 0 ) ;
  28.  
  29.        /* find first element to move left */
  30.        do { j = j - 1 ; } while( (*pcomp) (pa[j],ppart) > 0 ) ;
  31.  
  32.        if( i >= j)        /* have the boundaries met  */
  33.           break  ;        /* yes - through partitioning */
  34.  
  35.        /* swap i and j elements */
  36.        ptemp = pa[i] ; pa[i] = pa[j] ; pa[j] = ptemp ;
  37.     }
  38.  
  39.      nr = na - i ;        /* now deal with each partition */
  40.      if( i < (na/2) )
  41.     {  memsort( pa , i , pcomp) ;    /* sort left side */
  42.        memsort(&(pa[i]),nr,pcomp) ; /* sort right side */
  43.     }
  44.      else
  45.     {  memsort(&(pa[i]),nr,pcomp) ; /* sort right side */
  46.        memsort( pa , i , pcomp) ;    /* sort left side */
  47.     }
  48.   }
  49.  
  50.  
  51.